In a network where data streams may merge at a router the allocation of the network resources to the different streams in a fair way such that each stream receives an approximately equal share of the resources is a problem that has been addressed in a number of ways in the prior art.
Where a router receives say two streams then it can simply provide a fair arbitration scheme by selecting data streams alternately assuming the bandwidth of each data stream is the same. Where however, the router is downstream of a previous router, then one of the streams will contain data packets from two previous streams and thus, if the router is again allocated evenly between the input streams, the stream that has data packets from a single source will get the resource for half the time, while the stream with data packets from two sources will also get the resource for half the time meaning that the two streams from the earlier router will get the resource for a quarter of the time each, which would give the stream that comes directly to the router twice as much resource as the other streams.
An example of the above problem is shown in FIG. 1 where there are four sources of traffic A, B, C and D all requesting bandwidth at the same rate and being routed through routers 2, 4 and 6 that each have two inputs and one outputs. At the first router 2, C and D receive equal bandwidth. At the second router 4, B receives twice as much bandwidth as C or D and at the final router 6, A receives half of the available band width, B receives a quarter of the available bandwidth and C and D receive one eighth of the available bandwidth.
This problem has been addressed in the prior art in several different ways. In one solution a global timestamp is added to a data packet and when selecting a data packet for a resource the data packet with the oldest time stamp is selected. A problem with this solution is that the time stamp is relatively wide which adds to the bandwidth of the data stream. Furthermore, it is difficult to generate a global timestamp that provides a consistent view of time at different points in a network.
An alternative solution is one where the number of hops that a data packet makes is counted. The number of hops may be counted by incrementing a count value every time the data packet passes through a router. Where there is contention a data packet with the most hops can be preferentially selected. A problem with this is again that it adds information to the data packet increasing bandwidth requirements.
A still further solution is one where a master sends a marker with a data packet after it has sent a certain number of data packets and when allocating resources data packets from masters where a marker has not yet been received are prioritised. A disadvantage of this is that a record of whether or not markers have been received from each stream need to be kept and it is hard to deal with traffic from low latency sources or those that send little data.
It would be desirable to be able to provide an arbiter that can allocate resources in a fair manner to contending data packets without unduly increasing the bandwidth of the data traffic or the power and area requirements of the circuit